package com.moyoutian.leetcode.jianzhi;

/**
 *
 */
public class Demo04 {


    public static void main(String[] args) {

        int[][] matrix = new int[][]{{1}, {2}, {3}, {4}, {5}};
        System.out.println(findNumberIn2DArray(matrix, 5));
    }

    public static boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        //开始下标
        int rowBegin = 0;
        int lenBegin = 0;
        //结束下标
        int rowEnd = matrix.length - 1;
        int lenEnd = matrix[0].length - 1;

        int rowAvg = rowEnd;
        int lenAvg = rowEnd;

        //斜线上的数据二分查找,行列分别二分
        while (rowEnd > rowBegin || lenEnd > lenBegin) {
            rowAvg = (rowBegin + rowEnd + 1) / 2;
            lenAvg = (lenBegin + lenEnd + 1) / 2;
            if (matrix[rowAvg][lenAvg] == target || matrix[rowBegin][lenBegin] == target) {
                return true;
            } else if (matrix[rowAvg][lenAvg] > target) {
                rowEnd = rowAvg;
                lenEnd = lenAvg;
            } else {
                rowBegin = rowAvg;
                lenBegin = lenAvg;
            }
            if ((rowEnd - rowBegin == 1 || rowEnd == rowBegin) && (lenEnd - lenBegin == 1 || lenEnd == lenBegin)) {
                break;
            }
        }
        /**
         *          |
         *     y    |    x
         * --------------------
         *      z   |     g
         *          |
         *
         *z x区域的查找，因为g和y区域都不可能存在对应值
         * 先在z范围按行寻找
         */
        int row = rowEnd;
        int tempEnd = lenEnd;
        while (row < matrix.length) {
            if (matrix[row][0] == target) {
                return true;
            }
            //只有首不分小于目标值该行才有可能存在目标值
            else if (matrix[row][0] < target) {
                tempEnd = findRow(matrix, target, row, tempEnd);
                if (tempEnd == -1) {
                    break;
                } else {
                    //以后也不会有满足条件的数据
                    if (matrix[row][tempEnd] == target) {
                        return true;
                    }
                }
                row++;
            } else {
                break;
            }
        }
        /**
         *          |
         *     y    |    x
         * --------------------
         *      z   |     g
         *          |
         *
         *z x区域的查找，因为g和y区域都不可能存在对应值
         * 先在z范围按行寻找
         */
        int len = lenEnd;
        tempEnd = rowEnd;
        while (len < matrix[tempEnd].length) {
            if (matrix[0][len] == target) {
                return true;
            }
            //只有首不分小于目标值该行才有可能存在目标值
            else if (matrix[0][len] < target) {
                tempEnd = findL(matrix, target, len, tempEnd);
                if (tempEnd == -1) {
                    break;
                } else {
                    //以后也不会有满足条件的数据
                    if (matrix[tempEnd][len] == target) {
                        return true;
                    }
                }
                len++;
            } else {
                break;
            }
        }
        return false;
    }


    public static int findRow(int[][] matrix, int target, int row, int end) {
        int avg = end;
        int begin = 0;
        if (matrix[row][begin] < target) {
            while (end > begin) {
                avg = (begin + end + 1) / 2;
                if (matrix[row][avg] == target) {
                    return avg;
                } else if (matrix[row][begin] == target) {
                    return begin;
                } else if (matrix[row][avg] > target) {
                    end = avg;
                } else {
                    begin = avg;
                }
                if (end - begin == 1) {
                    return end;
                }
            }
        }
        return -1;
    }

    public static int findL(int[][] matrix, int target, int len, int end) {
        int avg;
        int begin = 0;
        if (matrix[begin][len] < target) {
            while (end > begin) {
                avg = (begin + end + 1) / 2;
                if (matrix[avg][len] == target) {
                    return avg;
                } else if (matrix[begin][len] == target) {
                    return begin;
                } else if (matrix[avg][len] > target) {
                    end = avg;
                } else {
                    begin = avg;
                }
                if (end - begin == 1) {
                    return end;
                }
            }
        }
        return -1;
    }
}
